package jd150

import "math"

/*
https://leetcode.cn/problems/triangle/?envType=study-plan-v2&envId=top-interview-150

120. 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：

	  2
	 3 4
	6 5 7

4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：
输入：triangle = [[-10]]
输出：-10
*/
func minimumTotal(triangle [][]int) int {

	n := len(triangle) //1.初始化数组
	f := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, n)
	}

	f[0][0] = triangle[0][0]
	for i := 1; i < n; i++ { //1.第一行遍历到最后一行
		f[i][0] = f[i-1][0] + triangle[i][0] //当前行的dp头元素,一定是当前行原数组元素+dp[i-1]行的头元素

		for j := 1; j < i; j++ { //从当前行第1列填充数组, 最后一列不要填充
			f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
		}
		f[i][i] = f[i-1][i-1] + triangle[i][i] //最后一列只能是上一行,前一列的dp值 + 当前行[i][i]元素
	}

	ans := math.MaxInt32 //获取到最后一行中的最小dp值, 就是最小的路径总和
	for i := 0; i < n; i++ {
		ans = min(ans, f[n-1][i])
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
